# -*- coding = utf-8 -*-
# @Time : 2021/11/30 13:53
# @Author : chenxingjia
# @File : 完全背包.py


# 基本解法
def complete_bag_0(weights, values, bag_weight):
    n = len(weights)
    dp = [[0 for _ in range(bag_weight+1)] for _ in range(n)]
    for i in range(n):
        for j in range(1, bag_weight+1):
            k = j // weights[i]
            for x in range(k+1):
                dp[i][j] = max(dp[i-1][j-x*weights[i]]+x*values[i], dp[i][j])

    return dp


# 优化1
def complete_bag_1(weights, values, bag_weight):
    n = len(weights)
    dp = [0 for _ in range(bag_weight+1)]
    for i in range(n):
        for j in range(bag_weight, weights[i]-1, -1):
            k = j // weights[i]
            for x in range(k+1):
                dp[j] = max(dp[j-x*weights[i]]+x*values[i], dp[j])
    return dp


# 优化2


def main():
    wights = [2, 2, 3, 1, 5, 2]
    values = [2, 3, 1, 5, 4, 3]
    bag_weight = 10
    res = complete_bag_1(wights, values, bag_weight)
    print(res)
    print(res[-1])


if __name__ == '__main__':
    main()